import java.util.PriorityQueue;

public class Solution4 {
    public void addNum(PriorityQueue<Integer> minHeap,PriorityQueue<Integer> maxHeap,int Num){
        if(maxHeap.isEmpty()){
            maxHeap.add(Num);
            return;
        }
        if(Num>=maxHeap.peek()){
            if(minHeap.size()<=maxHeap.size()){
                minHeap.add(Num);
            }
            else{
                minHeap.add(Num);
                maxHeap.add(minHeap.poll());
            }
        }
        else{
            if(maxHeap.size()<= minHeap.size()){
                maxHeap.add(Num);
            }
            else{
                maxHeap.add(Num);
                minHeap.add(maxHeap.poll());
            }
        }
    }

    public double getMedian(PriorityQueue<Integer> minHeap,PriorityQueue<Integer> maxHeap){
        if(minHeap.size()== maxHeap.size()){
            return (double)(minHeap.peek()+ maxHeap.peek())/2;
        }
        return minHeap.size()>maxHeap.size()? minHeap.peek() : maxHeap.peek();
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        for (int i:nums1) {
            addNum(minHeap,maxHeap,i);
        }
        for (int i:nums2) {
            addNum(minHeap,maxHeap,i);
        }
        return getMedian(minHeap,maxHeap);
    }

    public static void main(String[] args) {
        Solution4 s=new Solution4();
        System.out.println(s.findMedianSortedArrays(new int[]{1,2}, new int[]{3,4}));
    }
}
